#include <stdlib.h>
#include <stdio.h>
#include <time.h>
#include <math.h>
#include <iostream>
using namespace std;

#define B 2                 // 每个节点2个孩子节点
#define DomainSize 4        // 属性域大小，可以调整为4、8、16.....
#define MAX_NODES 1000      // 假设顺序表最多存储1000个节点

// 前缀树中节点的信息
typedef struct node {
    int parent;        // 父节点id
    int childs[B];     // 孩子节点id数组
    int bound;         // 边界
    double fre;        // 节点频率
} Node;

// 利用动态数组（顺序表）存放前缀树中节点
typedef struct list {
    int size;          // 记录顺序表中当前节点的个数
    Node* nodes;       // 记录顺序表地址
} List;

// 初始化顺序表
void init_list(List* tree_list) {
    tree_list->size = 0;
    tree_list->nodes = new Node[MAX_NODES];
}

// 阈值判断：输入树节点列表、节点的id、阈值，输出为判断结果（该节点是否需要拆分）
bool threshold_value(List* tree_list, int node_id, double threshold) {
    Node node = tree_list->nodes[node_id];
    if (node.parent == -1) { // 根节点
        return node.fre >= threshold;
    } else {
        Node parent = tree_list->nodes[node.parent];
        return (node.fre - parent.fre) >= threshold;
    }
}

// 子节点创建：输入树节点列表、父节点id、当前层数、属性域大小
void node_creation(List* tree_list, int parent_id, int level, int domainsize) {
    Node parent = tree_list->nodes[parent_id];
    int step = (domainsize >> level) / B;
    for (int i = 0; i < B; i++) {
        Node child;
        child.parent = parent_id;
        child.bound = parent.bound - (B - 1 - i) * step;
        child.fre = 0;
        tree_list->nodes[tree_list->size] = child;
        parent.childs[i] = tree_list->size++;
    }
}

// 子节点频率统计：输入前缀和数组、树节点列表、子节点id
void frequency_statistics(double* user_pricube, List* tree_list, int node_id) {
    Node node = tree_list->nodes[node_id];
    if (node.parent == -1) {
        node.fre = user_pricube[node.bound];
    } else {
        Node parent = tree_list->nodes[node.parent];
        node.fre = user_pricube[node.bound] - user_pricube[parent.bound];
    }
    tree_list->nodes[node_id] = node;
}

// 使用层序顺序构建前缀树：输入前缀和数组、属性域大小、阈值、树节点列表
void pritree_contruction(double* user_pricube, int domainsize, double threshold, List* tree_list) {
    // 初始化根节点
    Node root;
    root.parent = -1;
    root.bound = domainsize - 1;
    root.fre = user_pricube[domainsize - 1];
    tree_list->nodes[tree_list->size++] = root;

    // 层序遍历构建前缀树
    for (int i = 0; i < tree_list->size; i++) {
        Node node = tree_list->nodes[i];
        if (threshold_value(tree_list, i, threshold)) {
            node_creation(tree_list, i, log2(domainsize) - log2(node.bound + 1), domainsize);
            for (int j = 0; j < B; j++) {
                frequency_statistics(user_pricube, tree_list, node.childs[j]);
            }
        }
    }
}

// 采用先序遍历方式输出前缀树中叶节点的边界和频数：输入树节点列表、叶节点列表
void leaf_get(List* tree_list, List* leaf_list) {
    for (int i = 0; i < tree_list->size; i++) {
        Node node = tree_list->nodes[i];
        if (node.childs[0] == 0 && node.childs[1] == 0) {
            leaf_list->nodes[leaf_list->size++] = node;
        }
    }
}

// 最细粒度的划分
void fine_grained_division(List* leaf_list, double* estimate_pricube) {
    int domainsize = leaf_list->nodes[leaf_list->size - 1].bound;
    int leaf_num = leaf_list->size;
    int index = 0;

    // 细粒度划分
    for (int i = 0; i < leaf_num; i++) {
        if (i == 0) { // 第一个区间
            for (int j = 0; j <= leaf_list->nodes[i].bound; j++) {
                estimate_pricube[index++] = ((double)j + 1) / ((double)leaf_list->nodes[i].bound + 1) * leaf_list->nodes[i].fre;
            }
        } else { // 非第一个区间
            for (int j = 1; j <= leaf_list->nodes[i].bound - leaf_list->nodes[i - 1].bound; j++) {
                estimate_pricube[index++] = (double)j / ((double)leaf_list->nodes[i].bound - (double)leaf_list->nodes[i - 1].bound) * (leaf_list->nodes[i].fre - leaf_list->nodes[i - 1].fre) + leaf_list->nodes[i - 1].fre;
            }
        }
    }
}

int main() {
    int domainsize = DomainSize;  // 属性域的大小  域大小可以调整为4、8、16...
    // 输入样例
    double user_pricube[DomainSize] = {3, 5, 6, 7};
    double threshold = 3;

    List* tree_list = new List;
    List* leaf_list = new List;

    init_list(tree_list);
    init_list(leaf_list);

    // 前缀树构建
    pritree_contruction(user_pricube, domainsize, threshold, tree_list);

    cout << "以层序遍历方式输出前缀树所有节点：" << endl;
    for (int i = 0; i < tree_list->size; i++) {
        cout << tree_list->nodes[i].bound << ":" << tree_list->nodes[i].fre << '\t';
    }
    cout << endl;

    // 采用先序遍历方式输出前缀树中叶节点的边界和频数
    leaf_get(tree_list, leaf_list);

    cout << "以先序遍历方式输出前缀树叶子节点：" << endl;
    for (int i = 0; i < leaf_list->size; i++) {
        cout << leaf_list->nodes[i].bound << ":" << leaf_list->nodes[i].fre << '\t';
    }
    cout << endl;

    // 最细粒度的划分
    double estimate_pricube[DomainSize] = {0};
    fine_grained_division(leaf_list, estimate_pricube);

    cout << "前缀和估计值：" << endl;
    for (int i = 0; i < domainsize; i++) {
        cout << estimate_pricube[i] << '\t';
    }
    cout << endl;

    delete[] tree_list->nodes;
    delete tree_list;
    delete[] leaf_list->nodes;
    delete leaf_list;

    return 0;
}
